package j250222;

import java.util.Arrays;
import java.util.Random;

public class Main {
	 public static void qsort(int[] nums,int l,int r,int k){
		 int left=l-1,right=r+1;
	        int i=l;
	        int key=nums[new Random().nextInt(r-l+1)+l];
	        while(i<right){
	            if(nums[i]==key)i++;
	            else if(nums[i]<key){
	                int tmp=nums[++left];
	                nums[left]=nums[i];
	                nums[i]=tmp;
	                i++;
	            }
	            else if(nums[i]>key){
	                int tmp=nums[--right];
	                nums[right]=nums[i];
	                nums[i]=tmp;
	            }
	        }
	        //[l,left] [left+1,right-1] [right,r];
	        int a=left-l+1;
	        int b=right-l;
	        if(k<=a)  qsort(nums,l,left,k);
	        else if(k<=b) 
	            return ;
	        else  qsort(nums,right,r,k-b);
	        }
	    
	 public static void main(String[] args) {
		 int[] nums= {1,3,5,7,2,4,6,8};
		 int k=4;
		 int l=0,r=nums.length-1;
	        qsort(nums,l,r,k);
	        int[] ret=Arrays.copyOf(nums,k);
	        System.out.println(Arrays.toString(ret));
	    }
	    
	    
	public static void func(int[] ints) {
		ints[0]=666;
	}
		public static void main1(String[] args) {
			int[] nums= {1,2,3,4};
			int n=nums.length;
	        int left=-1,i=0,right=n;
	        while(i<right){
	            if(nums[i]==1)i++;
	            else if(nums[i]==0){
	                int tmp=nums[++left];
	                nums[left]=nums[i];
	                nums[i]=tmp;
	                i++;
	            }
	            else if(nums[i]==2){
	                int tmp=nums[--right];
	                nums[right]=nums[i];
	                nums[i]=tmp;
	            }
	        }
	        System.out.println(Arrays.toString(nums));
		}
}
